НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: МЕТОДИ ПОШУКУ У МАСИВАХ Варіант №12  Київ 2022 Мета: Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Теоретична частина Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних. Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого. Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку. Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних). Метод пошуку з бар’єром Ідея алгоритму: – у вихідний масив потрібно тимчасово включити шукане значення; – для одержання результату пошуку потрібно перевірити, чи дорівнює шукане значення тому елементу масиву, на якому відбулось завершення роботи алгоритму; – навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку; – після завершення пошуку потрібно повернути в кінець масиву початкове значення розміри масиву. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Метод пошуку з бар’єром Додаткові операції по установці і зняттю бар'єра окупаються спрощенням циклу, у якому витрачається основний час при пошуку. Особливо це позначиться при великих розмірах масиву. В загальному випадку час пошуку буде меншим, ніж у попередньому випадку. Звичайно у тому випадку, коли елементи масиву можуть повторюватись пошук не можна припиняти поки не перевірили всі елементи масиву до кінця. Тоді для практичної реалізації алгоритму потрібно застосувати цикл з лічильником, а пошук проводити до кінця масиву, це дасть можливість знайти всі відповідні елементи. У такому випадку кількість перевірок дорівнює - N. Пошук послідовності елементів в масиві Алгоритм прямого (послідовного) пошуку Ідея алгоритму: 1) i = 1, 2) порівняти i-й символ масиву T з першим символом масиву W, 3) збіг → порівняти другий символ і так далі, 4) розбіжність → i = i + 1 і перехід до пункту 2. Умова закінчення алгоритму: 1) підряд М порівнянь вдалі, 2) i + M > N, тобто слово не знайдене. Часова складність Метод Розмір Час виконання  Бар’єр 10х10 27 мкс   50х50 119 мкс   100х100 809 мкс  Пошук послідовності в масиві 10х10 25 мкс   50х50 42 мкс   100х100 49 мкс   Завдання: 1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом. Завдання до Варіанту_12
 Результати виконання лабораторної роботи:
Код: //Лабораторна робота №4_ПСА //ТР-15_Ткаченко_Майя, Варіант_12 #include <iostream> #include <chrono> using namespace std; void poshukbar(int *arr, int ex, int rozmir, int k){ int j=0; arr[rozmir] = ex; while(arr[j] != ex) { j++; } if(j == rozmir) { cout << ""; } else { cout << "<< ІНДЕКС >> шуканого елементу : [" << k << "][" << j << "]\n"; } } void poslidovnist(int *arr, int *p, int n, int M, int k){ bool flag = false; for(int j = 0; j < M - n + 1; j++){ for(int k = 0;k < n;k++) { if(arr[j + k] != p[k]) { break; } else if(k == n - 1) { cout << " Послідовність знаходиться за << ІНДЕКСОМ >>:[" << k << "][" << j << "]\n"; flag = true; } } } if(!flag) { cout << "";...